/* 

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */

/* 

所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

 */

// 递归
var lowestCommonAncestor = function (root, p, q) {
    if (root === null || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    /* 后序遍历 */
    // 如果左右子树的递归都有结果，说明 p 和 q 分居 root 的左右子树，返回 root。
    if (left !== null && right !== null) return root;
    // 如果两个子树递归结果都为 null，说明 p 和 q 都不在这俩子树中，返回 null。
    if (left === null && right === null) return null;
    // 由p 和 q 均存在于给定的二叉树中这个前提可知
    // 如果只是一个子树递归调用有结果，说明 p 和 q 都在这个子树，返回该子树递归结果。
    return left === null ? right : left;
};

// 非递归
var lowestCommonAncestor = function (root, p, q) {
    if (root === null || root === p || root === q) return root;
    const set = new Set();
    const map = new Map();
    const queue = [];
    queue.push(root);
    // 层序遍历
    while (queue.length) {
        let size = queue.length;
        while (size--) {
            const parent = queue.shift();
            if (parent.left) {
                queue.push(parent.left);
                // 记录父亲节点
                map.set(parent.left, parent);
            }
            if (parent.right) {
                queue.push(parent.right);
                // 记录父亲节点
                map.set(parent.right, parent);
            }
        }
    }
    // 构造 p 的上层节点集合
    while (p) {
        set.add(p);
        p = map.get(p);
    }
    while (q) {
        // 一旦发现公共节点重合，直接返回
        if (set.has(q)) return q;
        q = map.get(q);
    }
};